package com.lun.other.sort;

/**
 * 
 * 归并排序
 * 
 * from 《算法（第4版）》Robert Sedgewick、Kevin Wayne著 谢路云译
 * 
 * @author Jallen
 *
 */
public class Merge extends SortingAlgorithm{

	public static final boolean TOP_DOWN = true;
	public static final boolean BOTTOM_UP = false;
	
	private boolean mode;
	
	public Merge() {
		this(TOP_DOWN);
	}

	public Merge(boolean mode) {
		this.mode = mode;
	}
	
	@Override
	public void sort(int[] nums) {
		if(mode == TOP_DOWN) {
			sortTopDown(nums);
		}else {
			sortBottomUp(nums);
		}
	}
	
	private void sortTopDown(int[] nums) {
		int[] aux = new int[nums.length];
		sortTopDown(nums, aux, 0, nums.length - 1);
	}
	
	private void sortTopDown(int[] nums, int[] aux, int start, int end) {
		if(start >= end) return;
		int mid = start + (end - start) / 2;
		sortTopDown(nums, aux, start, mid);
		sortTopDown(nums, aux, mid + 1, end);
		merge(nums, aux, start, mid, end);
	}
	
	private void sortBottomUp(int[] nums) {
		int[] aux = new int[nums.length];
		for(int size = 1; size < nums.length; size *= 2) {
			for(int start = 0; start + size < nums.length; start += 2 * size) {
				merge(nums, aux, start, start + size - 1, // 
						Math.min(start + 2 * size - 1, nums.length - 1));
			}
		}
	}
	
	private void merge(int[] nums, int[] aux, int start, int mid, int end) {
		//将nums[start,mid]和nums[mid+1,end]归并
		int i = start, j = mid + 1;
		
		//将nums[start, end]复制到aux[start, end]
		for(int k = start; k <= end; k++) {
			aux[k] = nums[k];
		}

		//将aux[start, end]归并回到nums[start, end]
		for(int k = start; k <= end; k++) {
			if(i > mid) {
				nums[k] = aux[j++];
			}else if(j > end){
				nums[k] = aux[i++];
			}else if(aux[j] < aux[i]){//前两条条件相当于为后两条防止越界
				nums[k] = aux[j++];
			}else {
				nums[k] = aux[i++];				
			}
		}
	}

}
